# -*- coding: utf-8 -*-

class Solution:
    def __init__(self, nums, target):
        self.nums = nums
        self.target = target

    def twoSum(self):
        """

        :type nums:List[int]
        :type target:int
        :rtype: List[int]

        """
        for i in range(0, len(self.nums) - 1):
            for j in range(i + 1, len(self.nums)):
                if (self.nums[i] + self.nums[j]) == self.target:
                    return [i, j]


class HeapSort:
    def __init__(self, data_list):
        self.data_list = data_list

    # 排序方法sort method


    def BuildHeap(self, length):
        # 第一步：建堆 first step : build the heap
        if length >= 1:

            for i in range(length / 2 - 1, -1, -1):
                if self.data_list[i * 2 + 1] <= self.data_list[2 * i + 2]:
                    small = i * 2 + 1
                else:
                    small = i * 2 + 2
                if self.data_list[i] <= self.data_list[small]:
                    pass
                else:
                    tmp = self.data_list[i]
                    self.data_list[i] = self.data_list[small]
                    self.data_list[small] = tmp
        else:
            return self.data_list[0]

    # 第二步：调整堆 second Step: adjust the heap.In fact, the first step is just a step of adjust-heap


    def adjust(self):
        if len(self.data_list) >= 1:
            for i in range(len(self.data_list) - 1, -1, -1):
                tmp = self.data_list[0]
                self.data_list[0] = self.data_list[i]
                self.data_list[i] = tmp
                # 到这就破坏了原堆，因此需要重新建堆We need restruct the second heap because of original heap's the destruction
                self.BuildHeap(i - 1)

    def sort(self):
        self.BuildHeap(len(self.data_list))
        self.adjust()
        return self.data_list


class BinarySearch:
    def __init__(self, data_list):
        self.data_list = data_list

    def search(self, target):
        for i in range(0, len(self.data_list)):
            j = self.binarySearch(target - self.data_list[i])
            if j > 0:
                return[i,j]
            else:
                pass


    def binarySearch(self, target):
        low = 0
        high = len(self.data_list) - 1
        while low <= high:
            mid = (low + high) / 2
            if self.data_list[mid] == target:
                return mid
            elif self.data_list[mid] < target:
                low = mid + 1
            else:
                high = mid - 1

        return -1


def main():
    nums = [9, 2, 1, 7, 6, 8, 5, 3, 4]
    target = 12
    solu = Solution(nums, target)
    heap = HeapSort(nums)
    sort = heap.sort()
    print(sort)
    search = BinarySearch(nums)
    [i, j] = search.search(12)
    print([i,j])
    [i, j] = solu.twoSum()
    print([i, j])


if __name__ == '__main__':
    main()
